Syeikh Muhammad mula berdakwah di Basrah, tempat di mana beliau bermukim untuk menuntut ilmu ketika itu. Akan tetapi dakwahnya di sana kurang bersinar, kerana menemui banyak rintangan dan halangan dari kalangan para ulama tempatan. Di antara pendukung dakwahnya di Basrah ialah seorang ulama yang bernama Syeikh Muhammad al-Majmu’i. Tetapi mereka mendapat tekanan dan ancaman daripada sebahagian ulama dan diancam akan dibunuh yang menyebabkan beliau meninggalkan Basrah dan mengembara ke beberapa negeri Islam.

Setelah menjelajahi beberapa negeri islam, beliau kembali ke al-ihsa menemui gurunya Syeikh Abdullah bin `Abd Latif al-Ihsai untuk mendalami beberapa bidang pengajian tertentu yang selama ini belum sempat didalaminya. Di sana beliau bermukim untuk beberapa waktu, sebelum kembali ke kampung asalnya ‘Uyainah. Tidak lama selepas itu beliau mengikut orang tuanya ke Haryamla, suatu tempat di daerah Uyainah pada tahun 1139H kerana dikatakan terdapat perselisihan pendapat dengan pihak berkuasa Uyainah.

Syeikh Muhammad berpindah ke Uyainah pada tahun 1140H, dan tinggal bersama ayahnya untuk mengembangkan ilmu dan mengajar serta berdakwah selama lebih kurang 13 tahun lamanya, sehinggalah ayahnya meninggal dunia di sana pada tahun 1153. Setelah 13 tahun menegakkan amar ma’ruf dan nahi mungkar di Haryamla, beliau mengajak pihak penguasa setempat untuk bertindak tegas terhadap gerombolan penjahat yang selalu melakukan kerusuhan, merampas, merampok serta melakukan pembunuhan. Maka gerombolan tersebut tidak senang kepada Syeikh Muhammad, lalu mereka mengancam hendak membunuhnya. Syeikh Muhammad terpaksa meninggalkan Haryamla, dan kembali ke Uyainah.